package main

/*
Go语言的标准库中没有直接提供链表list的实现，使用container/list包来实现双向链表。链表是一种线性表的数据结构，其中的元素是通过指针相互连接的，列表有多种实现方法，如单链表、双链表等
list和slice的区别
1、底层结构：
切片是基于数组的动态数组抽象，具有指针、长度和容量。
列表是由节点通过指针相互连接的数据结构。
列表的存储的内存空间不连续，存在空间浪费，切片的存储空间连续
列表中是存储是一个元素的值和指向下一个元素位置的指针，存多个指针
切片由于存储空间连续，只存一个指针和元素之间的偏移量来确定其他元素的位置
2、操作灵活性：
切片提供了方便的动态操作，支持追加、切割等操作。
列表支持在任意位置插入和删除元素，但对于访问元素，需要从头或尾开始遍历。
3、性能特征：
切片在尾部追加元素的性能较好，时间复杂度为 O(1)。
列表在任意位置插入和删除元素的性能较好，时间复杂度为 O(1)。

*/
import (
	"container/list"
	"fmt"
)

func main() {
	/*
		一、list声明
	*/
	// 方式1
	var lsit1 list.List
	//方式2
	lsit2 := list.New()
	fmt.Println(lsit1)
	fmt.Println(lsit2)

	/*
		二、lsit的插入数据
	*/
	list3 := list.New()
	// 1、PushBack()，链表的末尾插入元素顺序python<-----java<-----go前面插入的在前面
	list3.PushBack("go")
	list3.PushBack("java")
	list3.PushBack("python")

	// 2、从链表头部插入元素，先插入的在后面，后面插入的在前面 1----->2----3
	list4 := list.New()
	list4.PushFront("1")
	list4.PushFront("2")
	list4.PushFront("3")

	/*
		三、遍历list
	*/
	// 1、正序遍历打印
	for i := list4.Front(); i != nil; i = i.Next() {
		// i := list4.Front()采用.Front()获取头节点，i.Next() 表示获取下一个节点
		fmt.Println(i.Value) // 3 2 1，因为list4是头部插入的，最后一个插入的3为第一个元素
	}

	// 2、反序遍历打印
	for e := list4.Back(); e != nil; e = e.Prev() {
		fmt.Println(e.Value) // 1 2 3
	}

	/*
		四、在特定元素前后插入元素
	*/
	list5 := list.New()
	list5.PushBack("go")
	list5.PushBack("java")
	list5.PushBack("python")
	list5.PushBack("vue")
	// list顺序为：第一个为go，其他的依次在后面插入  go--->java--->python--->vue
	//在java的前面插入"1"，在java插入"2"
	i := list5.Front() //定义一下i
	for ; i != nil; i = i.Next() {
		//遍历过程中判断值，获取java的位置
		if i.Value == "java" {
			break
		}
	}
	// InsertBefore(插入的值,插入的位置)在某个之前插入
	list5.InsertBefore("1", i)
	list5.InsertAfter("2", i)

	//再次遍历打印
	for j := list5.Front(); j != nil; j = j.Next() {
		fmt.Printf("%v ", j.Value) // go 1 java 2 python vue
	}
	fmt.Println()
	/*
		五、删除特定的元素
	*/
	// 删除前面python
	j := list5.Front() // 获取list5第一个元素位置
	for ; j != nil; j = j.Next() {
		// j != nil当j不是空的时候，不断获取j的下一个元素位置，直到j值为python
		if j.Value == "python" {
			break
		}
	}
	// 删除python
	list5.Remove(j)
	//再次遍历打印
	for j := list5.Front(); j != nil; j = j.Next() {
		fmt.Printf("%v ", j.Value) // go 1 java 2 python vue
	}
}

/*
list提供的方法：
type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element // 返回最后一个元素
func (l *List) Front() *Element // 返回第一个元素
func (l *List) Init() *List // 链表初始化
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素前插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某个元素后插入
func (l *List) Len() int // 返回链表长度
func (l *List) MoveAfter(e, mark *Element) // 把e元素移动到mark之后
func (l *List) MoveBefore(e, mark *Element) // 把e元素移动到mark之前
func (l *List) MoveToBack(e *Element) // 把e元素移动到队列最后
func (l *List) MoveToFront(e *Element) // 把e元素移动到队列最头部
func (l *List) PushBack(v interface{}) *Element // 在队列最后插入元素
func (l *List) PushBackList(other *List) // 在队列最后插入接上新队列
func (l *List) PushFront(v interface{}) *Element // 在队列头部插入元素
func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列
*/
